package com.gxc.stack;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;

/**
 * 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 *
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 */
public class LargestRectangleArea {

    public static void main(String[] args) {

        System.out.println(largestRectangleArea(new int[]{2,4}));
    }

    /**
     * 求两侧 比height[i]的最近坐标
     * @param heights
     * @return
     */
    public static int largestRectangleArea(int[] heights) {
        Deque<Integer> stack = new LinkedList<>();
        int max = 0;
        int[] left = new int[heights.length];
        Arrays.fill(left, -1);
        int[] right = new int[heights.length];
        Arrays.fill(right, heights.length);
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                Integer pop = stack.pop();
                right[pop] = i;
            }
            stack.push(i);
        }
        stack.clear();
        for (int i = heights.length-1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                Integer pop = stack.pop();
                left[pop] = i;
            }
            stack.push(i);
        }
        int res = 0;
        for (int i = heights.length - 1; i >= 0; i--) {
            res = (right[i] - left[i] - 1) * heights[i];
            max = Math.max(max, res);
        }
        return max;
    }

    public int largestRectangleArea2(int[] heights) {
        Deque<Integer> stack = new LinkedList<>(); // 存储索引
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            int currHeight = (i == n) ? 0 : heights[i]; // 处理最后一个元素

            // 当前高度小于栈顶元素，弹出栈顶并计算面积
            while (!stack.isEmpty() && currHeight < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }

            stack.push(i); // 当前索引入栈
        }

        return maxArea;
    }

}
